#include<bits/stdc++.h>
using namespace std;


class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int>ans;
        if(nums[0] >= 0){
            for(int i = 0; i < nums.size(); i++)ans.emplace_back(nums[i] * nums[i]);
        }
        else if(nums[nums.size() - 1] < 0){
            for(int i = nums.size() - 1; i >= 0; i--)ans.emplace_back(nums[i] * nums[i]);
        }
        else{
            int low = 0, high = nums.size(), mid;
            while(low < high){
                mid = (low + high) / 2;
                if(nums[mid] < 0)low = mid + 1;
                else high = mid;
            }
            int i = low - 1, j = low;
            while(true){
                if(i < 0){
                    for(; j < nums.size(); j++)ans.emplace_back(nums[j] * nums[j]);
                    break;
                }
                if(j >= nums.size()){
                    for(; i >= 0; i--)ans.emplace_back(nums[i] * nums[i]);
                    break;
                }
                if(abs(nums[i]) < abs(nums[j])){
                    ans.emplace_back(nums[i] * nums[i]);
                    i--;
                }
                else{
                    ans.emplace_back(nums[j] * nums[j]);
                    j++;
                }
            }
        }
        return ans;
    }
};

/**
 * @brief 2022.3.3
 * 可以先找到分界点，再双指针归并
 * 复杂度是 O(logn + n) = O(n)
 */